Computer networks have steadily increased in importance as more individual users, businesses, and other organizations send information to each other's computers by electronic distribution systems. Both local networks, such as Local Area Networks (LANs) within an organization, and wide area networks (WANs), such as the Internet, have widespread use. With many different local networks communicating with each other over wide area networks, data must be routed through different connections using a variety of networking protocols. One widely-used protocol for use with the Internet is the Border Gateway Protocol (BGP). This is an exterior gateway protocol (EGP), i.e., an interautonomous system routing protocol, meaning that it is used to carry routing information externally between different Autonomous Systems (AS's). An AS is, for example, a particular computer network or group of networks under a common administration and with common routing policies that can communicate with another AS via a WAN such as the Internet.
In implementing the BGP, an AS can include one or more routers to receive data from and send data to other (AS's). For BGP routes, the router looks up routing information based on received data packets. Using an Interior Gateway Protocol (IGP), the router then forwards the data to a proper destination address (port) based on the routing information, whether that port be within the AS of the router (e.g. on an internal network), or eventually out to another router of another AS.
A router finds the outgoing interface of each incoming packet by querying a routing table stored in that router. For example, a router uses the destination address of every incoming packet to decide the proper next-hop information of the packet from the table, i.e. the information describing the address of the next router in the route to the destination of that packet.
The lookup of routing information takes time, and it can be difficult in many implementations to achieve transfers at full wire speeds, i.e. at the maximum speed of data transfer allowed by the communication channel. Resolving BGP routes are time consuming for a variety of reasons. For example, a Longest Prefix Match (LPM) search is often performed to find more efficient routes. This type of search finds the longest prefix match (matched address) of the destination address from all of the prefixes stored in the router, and can be used to find an appropriate forwarding port for routers and layer 3 switches. This kind of search may require two accesses of “leaves” of a “tree” in memory: one access being a read operation to obtain the pattern contained in the forwarding leaf for a “compare-at-end” operation, and the second access being a second read operation to backtrack to the longest match if the compare-at-end operation fails. Thus, this operation may require two accesses to leaf memory.
Another reason for potential time delay in relaying data for BGP routes is the organization of routing addresses. For BGP routes, a first lookup in the memory tree returns a next-hop value that is used as the key for a second tree search operation. The second lookup in the tree returns the needed IGP routing information. This two-level lookup allows for a smaller number of entries in the routing table to be updated when there are topology changes in the AS, since external routes do not have to be updated when internal routes change within an AS. However, having to do this second lookup requires another potential two memory accesses to leaf memory, slowing down transmission times.
In any given router design, there is a cycle budget that can be calculated based on the repeated arrival of packets having a minimum length. To maintain wire speed routing, the processor in the router must complete all of its operations under this cycle budget. Accessing memory as many as four times for a BGP route severely limits the speed of the data transmission.
Accordingly, what is needed is a system and method for reducing the access of memory when resolving BGP or other external gateway protocol routes. The present invention addresses such a need.